In an IP-network information is transmitted between hosts through routers placed at the edge of and inside the network, see FIG. 1. An IP-network is an example of a packet network which generally uses a multitude of switching elements connecting terminals placed at the edge of network. A packet based network can generally support variable bit rate services, such as different codings of speech and data services, much better than an STM (Synchronous Transfer Mode) network, since statistical multiplexing can be used. The multiplexing gain in packet networks improves e.g. the number of speech/data channels that can be used to transmit information between the terminals. Operation and maintenance of packets networks can be simplified compared to STM networks and the traffic associated therewith be multiplexed with other traffic.
However, when the traffic flow on a link between e.g. two routers in an IP-network is too high, congestion can occur and then some packets must be discarded, since otherwise the real-time demands of some of the traffic will not be fulfilled. The new technologies that allows the use of IP-network also for voice traffic introduce different levels of service for different traffic types. Voice traffic is very sensitive to delay and jitter, but data is more sensitive to loss of packets. Thus, a separation of the levels of QoS (Quality of Service) is needed between voice and data traffic. QoS separation is the capability of a network to provide a better service for selected network traffic, i.e to treat different classes of traffic differently. An architecture providing QoS separation is the Differentiated Services, DiffServ, as proposed by the IETF, the Internet Engineering Task Force. Still, this architecture lacks some performance so there is a need for improved solutions.
One of the main causes of congestion in packet switched networks comprises that the traffic is often bursty. If the traffic was uniform, such as e.g. in circuit switched telephony, it would be easy to predict its behaviour and dimension the networks accordingly. In the packet data case, dimensioning is much more difficult and requires weighting between packet loss, induced delay and efficient usage of bandwidth.
To use the bandwidth efficiently, the bursts must be smoothed out in time. This is done by using buffers in the routers in which packets will be queued until the link is ready—a delay is thus induced in the queue—and it is regarded as implicit traffic shaping. This works well when the average traffic flow over a period of time is less then the egress bandwidth but when the ingress traffic over a period of time exceeds this limit, some packets must be discarded.
Policing is a general term for the process of preventing a traffic stream from seizing more than its share of the resources, i.e. to protect the network from non-trusted users. Policing can be done for the aggregated flow, for the separate service classes of DiffServ or for the packet flow of individual users. Policing acts in a short time perspective and actions take place locally, at the router level. The policing function consists of two different parts, metering and discarding. Metering is the function that monitors the arrival times of packets of a traffic stream and determines the level of conformance of each packet to a pre-established traffic profile.
The meter function should be able to handle bursty traffic and at the same time utilize the bandwidth on the egress link efficiently. When congestion is indicated, the discarding function is activated, deciding whether to transmit or discard the arriving packets. This decision will depend on several parameters such as aggregated flow, class based flow, QoS class of the packet, etc. Discarding can also take place in a scheduler, i.e. that part of a router which actually forwards the packets, but it is preferable that all of the dropping takes place in the policer because of the unpredictable manner in which packets are dropped in a scheduler.
When the traffic to a large extent consists of voice packets, the delay demands are so important that the scheduler should be a priority scheduler, provided that the voice traffic is assigned a high priority traffic class. A priority scheduler always serves the non-empty queue of highest priority. This might cause starvation of the lower priority traffic but it can also imply too long delays to the high priority traffic if too much traffic is let through, i.e. it will cause too long queues in the scheduler.
One known solution to this problem, i.e. how to police the traffic flow in order to fulfil the demands of the different traffic classes, is to use a Token Bucket procedure as the policer, see A. Tannenbaum, “Computer Networks—Third Edition” Prentice Hall 1996, pp. 381-384. The Token Bucket procedure monitors the packets of the incoming traffic stream and discards the packets that are out of profile compared to a pre-established traffic profile. When using the Token Bucket procedure, a priority scheduler can-be used.
There are several other mechanisms that can be used for policing e.g. WFQ (Weighted Fair Queuing), CBQ (Class Based Queuing) but the fact that they do not provide a strict priority to higher priority classes makes them less useful for real-time applications.
In the article E. P. Ratgeb, “Modelling and Performance Comparison of Policing Mechanisms for ATM Networks”, IEEE Journal on selected areas in communications. Vol. 9, No. 3, April 1991, some policing procedures that are “window-based” are discussed and evaluated, including also a “Moving Window” procedure, herein called the Sliding Window procedure.
When using a priority scheduler, there is a risk that traffic of lower priority will suffer from “starvation”, i.e. the queues will not be served, as has been mentioned above. This is very critical in networks in which traffic classes of different priorities have real time demands. To guarantee that such starvation will not occur, there must be a functionality that polices, i.e. meters the traffic flow and discards packets that are out of profile, the traffic flow so that a certain traffic class does not overuse its share of bandwidth. This also protects a traffic class from delaying “itself” too long. Too much traffic in the queue will introduce a too long delay. The IETF proposed the Token Bucket procedure as a policer. The proposed procedure have some properties that are not desirable, especially in the case where the traffic mainly comprises voice traffic. In addition to voice traffic, there are also other real time classes. The undesirable properties comprise that during the time period following immediately after a congestion has been indicated traffic classes of lower priority might suffer from starvation, and that a strict upper limit of the induced delay can not be guaranteed. This results from the fact that the Token Bucket procedure has a reaction time due to the bucket size, which gives a high probability that the bucket is full when congestion is indicated.
Another important aspect is how to measure the aggregated flow when using the Token Bucket procedure. This measurement is required to allow the use of “soft policing”. Soft policing means that the policing is only performed when the aggregated flow is above a certain threshold. The Token Bucket procedure has two parameters, the token rate and the bucket size. The token rate is the rate with which the bucket is filled with tokens so it does not tell anything about the flow. The only parameter that tells anything about the flow situation is the present amount of tokens in the bucket, but there is no easy way to use that information to calculate the aggregated flow. This means that some flow meter for the aggregated flow has to be added.
For the Token Bucket procedure to work properly it must be calibrated for the worst case traffic scenario in a network. This might give bad qualities for the other possible traffic cases that can occur in the network.